package graph;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * create by yongli on 2021-03-15 22:54
 * 图有多种存储方式, 使用不同的图，为不同的问题提供了方便
 * 为简化图操作，比如Data统一为Integer
 */

public class GraphVertexAndEdge {
    List<Vertex> vertices;
    // 通过hashMap直接索引到其指向的节点
    HashMap<Vertex,List<Edge>> map;

    public void add(Vertex vertex){
        vertices.add(vertex);
    }
    // 需要用户首先建立好变，默认合法，不会进行检查。
    public void add(Edge edge){
        Vertex src = edge.src;
        map.get(src).add(edge);
    }
     // 要求传递的对象就是它
    public  void delete(Vertex vertex){
        vertices.remove(vertex);
        map.remove(vertex);
        for(Vertex key:map.keySet()){
            List<Edge> edges = map.get(key);
            edges.removeIf(edge -> edge.dst==vertex);
        }
    }

    // 任给一个节点
    public void dfs(Vertex vertex){
        if(!vertex.isVisited){
            print(vertex);
        }
        List<Edge> edges = map.get(vertex);
        // 流操作
        List<Vertex> vertices = edges.stream().map((edge -> edge.dst)).collect(Collectors.toList());
        // 深度遍历
        vertices.forEach(this::dfs);
    }

    public void bfs(Vertex vertex){


    }


    public void print(Vertex vertex){

    }

}

// 结点的标识使用name，没有规律，可以采用数组索引。
// 比如说给结点增加属性，比如增加是否访问的字段
// 结点集合和边集合
//
class Vertex{
    Integer data;
    boolean isVisited;
}
// 有向图
class Edge{
    Vertex src;
    Vertex dst;
    Integer weight;
}

